#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdio>
using namespace std;
#define REP(i, n) for(int i=0; i<int(n); i++)
typedef long long LL;
const int MOD = 1000000007;
//const int MOD = 2;
int powMod(int x, int n){
    int res = 1;
    for(; n; n>>=1, x=(LL)x*x%MOD)
        if(n&1)res=(LL)x*res%MOD;
    return res;
}
int inv(int x){
    return powMod(x, MOD-2);
}
#define MAXN 100020
int f[MAXN];
bool vis[MAXN];
void init_euler(){
    for(int i = 0; i < MAXN; i++)f[i] = i;
    for(int i = 2; i < MAXN; i++){
        if(!vis[i]){
            for(int j = i; j < MAXN; j+=i){
                f[j] -= f[j] / i;
                vis[j] = true;
            }
        }
    }
}
int p[MAXN], q[MAXN];
int C(int n, int m){
    if(n<m||m<0||n<0)return 0;
    return (LL)p[n]*q[m]%MOD*q[n-m]%MOD;
}
//n blocks, totally m people, no more than k consecutive people
inline int calc(int n, int m, int k){
    int res = 0, t;
    for(int i = 0; (t = m + n - i * k - 1) >= n-1 && i <= n; i++){
        res = (res + ((i&1)?-1:1) * (LL)C(n, i) * C(t, n-1)) % MOD;
    }
    return (res + MOD) % MOD;
}

int m, k;

int polya(int n){
    int res = 0;
    for(int i = 1; i * i <= n; i ++){
        if (n % i) continue;
        int j = n / i;
        if(m % j == 0)res = (res + (LL)calc(i, m / j, k) * f[j]) % MOD;
        if (j!=i && m % i == 0) res = (res + (LL)calc(j, m / i, k) * f[i]) % MOD;
    }
    res = res * (LL) inv(n) % MOD;
    return res;
}

int main()
{
    //freopen("in", "r", stdin);
    int n;
    p[0] = 1; q[0] = 1;
    for (int i = 1; i < MAXN; i++) p[i] = p[i-1] * (LL)i % MOD, q[i] = inv(p[i]);
    init_euler();
    int T;
    scanf("%d", &T);
    REP(tt, T){
        scanf("%d%d%d", &n, &m, &k);
        printf("Case #%d: ", tt + 1);
        if(m==n){
            if(n<k){
                puts("1");
            } else {
                puts("0");
            }
        } else {
            printf("%d\n", polya(n-m));
        }
    }
}